package 面试题;

/**
 * 求根号a
 * a表示求的是根号a，k表示小数保留几位
 * 牛顿迭代法：
 * 1、构建 y = x方 - a
 * 2、(b，b-a方)处的切线为 y-(b-a方)= 2b(x-b)，得到 y=2bx-b方-a
 * 3、切线与x轴交点的横坐标为 (b方+a)/2b
 * 4、将这个横坐标作为新的b，重复2、3、4步骤
 */
public class 根号a {
    //牛顿迭代法（推荐）
    public double helper(int a, int k) {
        double b = a;
        while (String.valueOf(b).length() <= k + 1) {
            b = (b * b + a) / (2 * b);
        }
        return b;
    }

    //二分法
    public double helper2(int a, int k) {
        double l = 0;
        double r = a;
        double mid = (l + r) / 2;
        while (String.valueOf(mid).length() <= k + 1) {
            if (mid * mid <= a) {
                l = mid;
            } else {
                r = mid;
            }
            mid = (l + r) / 2;
        }
        return mid;
    }

    public static void main(String[] args) {
        根号a t = new 根号a();
        //求根号2
        int a = 2;
        //小数保留10位
        int k = 10;

        double res = t.helper(a, k);
        System.out.println(res);

        double res2 = t.helper2(a, k);
        System.out.println(res2);
    }
}
